import java.util.Stack;

public class TreeNode2 {
    int val;
    TreeNode2 left;
    TreeNode2 right;

    TreeNode2(int x) {
        val = x;
    }


    class Solution {
        //找两个结点的公共祖先
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

            Stack<TreeNode> stackP = new Stack<>();
            Stack<TreeNode> stackQ = new Stack<>();
            getPath(root, p, stackP);
            getPath(root, q, stackQ);
            int size_P = stackP.size();
            int size_Q = stackQ.size();
            if (size_P > size_Q) {
                int count = size_P - size_Q;
                while (count != 0) {
                    stackP.pop();
                    count--;
                }
            } else {
                int count = size_Q - size_P;
                while (count != 0) {
                    stackQ.pop();
                    count--;
                }

            }
            while (!stackP.isEmpty() && !stackQ.isEmpty()) {
                if (stackP.peek() == stackQ.peek()) {
                    return stackP.peek();
                } else {
                    stackP.pop();
                    stackQ.pop();
                }
            }
            return null;

        }

        public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
            if (root == null) {
                return false;
            }
            stack.push(root);
            if (root == node) {
                return true;
            }
            TreeNode cur = root;
            boolean ret = getPath(root.left, node, stack);
            if (ret) {
                return true;
            }
            ret = getPath(root.right, node, stack);
            if (ret) {
                return true;
            }
            stack.pop();
            return false;
        }
    }
}